{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "def binarySearch(array, start, end, target):              # T(N)\n",
    "    mid = (start+end)/2                                   # O(1)\n",
    "    if array[mid] == target:                              # O(1)\n",
    "        return True                                       # O(1)\n",
    "    elif array[mid] > target:                             # O(1)\n",
    "        binarySearch(array, start, mid-1, target)         # T(N/2)\n",
    "    else:\n",
    "        binarySearch(array, mid+1, end, target)           # T(N/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$T(N) = O(1) + T(N/2)$$\n",
    "\n",
    "假设$$N=2^M$$\n",
    "\n",
    "$$T(N) = T(N/2) + O(1) = T(2^{M-1}) + O(1) = T(2^{M-2}) + 2O(1)=...=T(2^{M-M}) + MO(1)=O(M)$$\n",
    "\n",
    "而$$M=logN$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "165580141\n",
      "53.53498697280884\n"
     ]
    }
   ],
   "source": [
    "def fib(N):\n",
    "    if N == 0:\n",
    "        return 1\n",
    "    if N == 1:\n",
    "        return 1\n",
    "    if N > 1:\n",
    "        return fib(N-1) + fib(N-2)\n",
    "    \n",
    "import time\n",
    "t1 = time.time()\n",
    "print(fib(40))\n",
    "t2 = time.time()\n",
    "print(t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$T(N) = T(N-1) + T(N-2)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "165580141\n",
      "0.00018906593322753906\n"
     ]
    }
   ],
   "source": [
    "def fib(N):\n",
    "    if N == 0:\n",
    "        return 1\n",
    "    if N == 1:\n",
    "        return 1\n",
    "    arr = [1 for i in range(N+1)]\n",
    "    for i in range(2, N+1):\n",
    "        arr[i] = arr[i-1] + arr[i-2]\n",
    "    return arr[N]\n",
    "\n",
    "import time\n",
    "t1 = time.time()\n",
    "print(fib(40))\n",
    "t2 = time.time()\n",
    "print(t2-t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [0 * 10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```py\n",
    "def quicksort(arr, p, r):             # T(N)\n",
    "    if p < r:                         # O(1)\n",
    "        q = partition(arr, p, r)      # O(N)\n",
    "        quicksort(arr, p, q-1)        # T(N/2) -> T(N-1)\n",
    "        quicksort(arr, q+1, r)        # T(N/2)\n",
    "```\n",
    "\n",
    "递推公式为：\n",
    "\n",
    "$$T(N) = 2T(N/2) + O(N)$$\n",
    "\n",
    "假设$$N=2^M$$\n",
    "\n",
    "$$T(N)=T(2^M)=2T(2^{M-1}) + O(2^M)$$\n",
    "\n",
    "又因为$$T(2^{M-1})=2T(2^{M-2})+O(2^{M-1})$$\n",
    "\n",
    "又因为$$T(2^{M-2})=2T(2^{M-3})+O(2^{M-2})$$\n",
    "\n",
    "所以\n",
    "\n",
    "$$T(2^{M})=2^2 * T(2^{M-2}) + O(2^M) + 2O(2^{M-1})=2^2 * T(2^{M-2})+2 * 2^M * O(1)=2^M * T(1) + M * 2^M * O(1)=(M+1)*2^M*O(1)=O(NlogN)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最坏情况递推公式变为$$T(N)=T(N-1)+O(N)=T(N-2)+N*O(1)+(N-1)*O(1)=O(N^2)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
